//
// Created by Jisam on 24/08/2024 7:40 PM.
// Solution of  c
#pragma GCC optimize(3)

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include<climits>

using namespace std;

#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while((ch>'9'||ch<'0')&&ch!='-')
        ch=getchar();
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int mod=100003;
int n,m,x,y,tot=0;
const int N=1000005,M=4000005;
int head[N],to[M],nxt[M],d[N],ans[N];
bool p[N];
priority_queue< pair< int,int > > q;
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int main()
{

    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=1e9;p[i]=0;
    }
    d[1]=0;ans[1]=1;
    q.push(make_pair(0,1));
    while(q.size())
    {
        x=q.top().second;
        q.pop();
        if(p[x])	continue;
        p[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            y=to[i];
            if(d[y]>d[x]+1)
            {
                d[y]=d[x]+1;
                ans[y]=ans[x];
                q.push(make_pair(-d[y],y));
            }
            else if(d[y]==d[x]+1)
            {
                ans[y]+=ans[x];
                ans[y]%=mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if()
    int ok = 0;
    for(int i = 0; i < m ; i ++){
        if(st[i] == 1){
            ok = 1;
            break;
        }
    }
    if(ok)cout << 1 <<endl;
    else cout << 0 << endl;
    return 0;
}

